.TH std::ranges::rotate 3 "2024.06.10" "http://cppreference.com" "C++ Standard Libary"
.SH NAME
std::ranges::rotate \- std::ranges::rotate

.SH Synopsis
   Defined in header <algorithm>
   Call signature
   template< std::permutable I, std::sentinel_for<I> S >

   constexpr ranges::subrange<I>                         \fB(1)\fP \fI(since C++20)\fP

       rotate( I first, I middle, S last );
   template< ranges::forward_range R >

   requires std::permutable<ranges::iterator_t<R>>       \fB(2)\fP \fI(since C++20)\fP
   constexpr ranges::borrowed_subrange_t<R>

       rotate( R&& r, ranges::iterator_t<R> middle );

   1) Performs a left rotation on a range of elements. Specifically, ranges::rotate
   swaps the elements in the range [first, last) in such a way that the element *middle
   becomes the first element of the new range and *(middle - 1) becomes the last
   element.
   The behavior is undefined if [first, last) is not a valid range or middle is not in
   [first, last).
   2) Same as \fB(1)\fP, but uses r as the range, as if using ranges::begin(r) as first and
   ranges::end(r) as last.

   The function-like entities described on this page are niebloids, that is:

     * Explicit template argument lists cannot be specified when calling any of them.
     * None of them are visible to argument-dependent lookup.
     * When any of them are found by normal unqualified lookup as the name to the left
       of the function-call operator, argument-dependent lookup is inhibited.

   In practice, they may be implemented as function objects, or with special compiler
   extensions.

.SH Parameters

   first, last - the range of elements to rotate
   r           - the range of elements to rotate
   middle      - the iterator to the element that should appear at the beginning of the
                 rotated range

.SH Return value

   {new_first, last}, where new_first compares equal to ranges::next(first,
   ranges::distance(middle, last)) and designates a new location of the element pointed
   by first.

.SH Complexity

   Linear at worst: ranges::distance(first, last) swaps.

.SH Notes

   ranges::rotate has better efficiency on common implementations if I models
   bidirectional_iterator or (better) random_access_iterator.

   Implementations (e.g. MSVC STL) may enable vectorization when the iterator type
   models contiguous_iterator and swapping its value type calls neither non-trivial
   special member function nor ADL-found swap.

.SH Possible implementation

   See also the implementations in libstdc++ and MSVC STL.

   struct rotate_fn
   {
       template<std::permutable I, std::sentinel_for<I> S>
       constexpr ranges::subrange<I>
           operator()(I first, I middle, S last) const
       {
           if (first == middle)
           {
               auto last_it = ranges::next(first, last);
               return {last_it, last_it};
           }
           if (middle == last)
               return {std::move(first), std::move(middle)};

           if constexpr (std::bidirectional_iterator<I>)
           {
               ranges::reverse(first, middle);
               auto last_it = ranges::next(first, last);
               ranges::reverse(middle, last_it);

               if constexpr (std::random_access_iterator<I>)
               {
                   ranges::reverse(first, last_it);
                   return {first + (last_it - middle), std::move(last_it)};
               }
               else
               {
                   auto mid_last = last_it;
                   do
                   {
                       ranges::iter_swap(first, --mid_last);
                       ++first;
                   }
                   while (first != middle && mid_last != middle);
                   ranges::reverse(first, mid_last);

                   if (first == middle)
                       return {std::move(mid_last), std::move(last_it)};
                   else
                       return {std::move(first), std::move(last_it)};
               }
           }
           else
           { // I is merely a forward_iterator
               auto next_it = middle;
               do
               { // rotate the first cycle
                   ranges::iter_swap(first, next_it);
                   ++first;
                   ++next_it;
                   if (first == middle)
                       middle = next_it;
               }
               while (next_it != last);

               auto new_first = first;
               while (middle != last)
               { // rotate subsequent cycles
                   next_it = middle;
                   do
                   {
                       ranges::iter_swap(first, next_it);
                       ++first;
                       ++next_it;
                       if (first == middle)
                           middle = next_it;
                   }
                   while (next_it != last);
               }

               return {std::move(new_first), std::move(middle)};
           }
       }

       template<ranges::forward_range R>
       requires std::permutable<ranges::iterator_t<R>>
       constexpr ranges::borrowed_subrange_t<R>
           operator()(R&& r, ranges::iterator_t<R> middle) const
       {
           return (*this)(ranges::begin(r), std::move(middle), ranges::end(r));
       }
   };

   inline constexpr rotate_fn rotate {};

.SH Example

   ranges::rotate is a common building block in many algorithms. This example
   demonstrates insertion sort.


// Run this code

 #include <algorithm>
 #include <iostream>
 #include <numeric>
 #include <string>
 #include <vector>

 int main()
 {
     std::string s(16, ' ');

     for (int k {}; k != 5; ++k)
     {
         std::iota(s.begin(), s.end(), 'A');
         std::ranges::rotate(s, s.begin() + k);
         std::cout << "Rotate left (" << k << "): " << s << '\\n';
     }
     std::cout << '\\n';

     for (int k {}; k != 5; ++k)
     {
         std::iota(s.begin(), s.end(), 'A');
         std::ranges::rotate(s, s.end() - k);
         std::cout << "Rotate right (" << k << "): " << s << '\\n';
     }

     std::cout << "\\nInsertion sort using `rotate`, step-by-step:\\n";

     s = {'2', '4', '2', '0', '5', '9', '7', '3', '7', '1'};

     for (auto i = s.begin(); i != s.end(); ++i)
     {
         std::cout << "i = " << std::ranges::distance(s.begin(), i) << ": ";
         std::ranges::rotate(std::ranges::upper_bound(s.begin(), i, *i), i, i + 1);
         std::cout << s << '\\n';
     }
     std::cout << (std::ranges::is_sorted(s) ? "Sorted!" : "Not sorted.") << '\\n';
 }

.SH Output:

 Rotate left \fB(0)\fP: ABCDEFGHIJKLMNOP
 Rotate left \fB(1)\fP: BCDEFGHIJKLMNOPA
 Rotate left \fB(2)\fP: CDEFGHIJKLMNOPAB
 Rotate left \fB(3)\fP: DEFGHIJKLMNOPABC
 Rotate left \fB(4)\fP: EFGHIJKLMNOPABCD

 Rotate right \fB(0)\fP: ABCDEFGHIJKLMNOP
 Rotate right \fB(1)\fP: PABCDEFGHIJKLMNO
 Rotate right \fB(2)\fP: OPABCDEFGHIJKLMN
 Rotate right \fB(3)\fP: NOPABCDEFGHIJKLM
 Rotate right \fB(4)\fP: MNOPABCDEFGHIJKL

 Insertion sort using `rotate`, step-by-step:
 i = 0: 2420597371
 i = 1: 2420597371
 i = 2: 2240597371
 i = 3: 0224597371
 i = 4: 0224597371
 i = 5: 0224597371
 i = 6: 0224579371
 i = 7: 0223457971
 i = 8: 0223457791
 i = 9: 0122345779
 Sorted!

.SH See also

   ranges::rotate_copy copies and rotate a range of elements
   (C++20)             (niebloid)
   ranges::reverse     reverses the order of elements in a range
   (C++20)             (niebloid)
   rotate              rotates the order of elements in a range
                       \fI(function template)\fP
